package Math;

class divide {
    public int divide(int dividend, int divisor) {
        //divisor>>1 == divisor/2
        if(dividend==0){
            return 0;
        }
        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        boolean negative;
        negative = (dividend ^ divisor) <0;//用异或来计算是否符号相异
        long t = Math.abs((long) dividend);
        long d= Math.abs((long) divisor);
        int result = 0;
        /**
         当dividend 为100，divisor 为3. 100/2^n 大于等于divisor时，即至少有2^n个divisor
         然后dividend减去2^n个divisor，继续计算得到最后结果
         */
        for(int i=31;i>=0;i--){
            if((t>>i)>=d){  //找出足够大的数 divisor * 2^n

                result += 1<<i; //将结果加上2^n
                t -= d<<i; //将被除数减去2^n*divisor
            }
        }
        return negative ? -result : result;//符号相异取反
    }
}

